1. Field of the Invention
The present invention relates to a method for finding a minimal signed digit with variable multi-bit coding; and, more particularly, to a method for finding a minimal signed digit with variable multi-bit coding based on Booth's algorithm.
This work was supported by the IT R&D program for MIC/IITA [2005-S-405-02, “A Development of the Next Generation Internet Server Technology”].
2. Description of Related Art
A conventional variable multi-bit coding scheme can be applied to multiplication and matrix operations using a fixed multiplier. These operations are the ones required for digital filters or various kinds of transforms such as Discrete Cosine Transform (DCT), and Inverse DCT (IDCT).
Especially, the conventional variable multi-bit coding scheme exhibits high efficiency in terms of speed and area consumption in the multiplication operation because it can obtain a partial product to conduct the multiplication operation with only simple wiring of data path.
Meanwhile, among methods of reducing the number of partial products generated in the multiplication operation, one of them is well-known to reduce the number of partial products by finding Minimal Signed Digit (MSD) with Canonical Signed Digit (CSD). Such a method has to find corresponding values in a table one by one in bitwise scanning manner.
In addition, there is also another method which reduces the number of partial products by finding MSD with variable multi-bit based on Booth's algorithm.
As well-known in the art, according to the Booth's algorithm, the partial product generated by overlapping a multiplier in 2-bit units and then coding the same in the multiplication operation is implemented only by shift and addition operations. The Booth's algorithm is modified to be coded in 3-bit units by MacSorley, and Sam and Gupta proved that another Booth's algorithm can be applied from 3-bit to multi-bit. These Booth's algorithms commonly code a digit represented in a bit form by adding lower bits thereto and then overlapping this with their previous bits. Particularly, this coding is done by shifting the digit by a given length.
FIG. 1 is a view conceptually illustrating an example of a conventional method of applying Booth's algorithm to multi-bit in 2's complement representation.
Referring to FIG. 1, an n-bit digit 101 in 2's complement representation in the prior art is represented for each bit as a given n-bit multiplier Y in the multiplication operation.
First, in order to apply Booth's algorithm to the n-bit digit 101 in 2's complement representation, “0” is given to “y−1” which is Least Significant Bit (LSB), as in the general Booth's algorithm. In addition, indexes are initialized as follows: m=0 and k=2.
Next, shift and scanning 102 are started from after k=3 by using the index values as above. Here, “m−1” denotes the location of LSB of a group selected for coding and “k” denotes the number of bits of a group selected for coding. At this time, the group 103 is designated as a group for k greater than 3 including LSB if one of bits within the group is “1” and the reset thereof is “0”, or if one bit is “0” and the rest thereof is “1”. Further, the group may be designated a group even when “1” is continuous from the lower bits or the upper bits.
The result of group designated as above corresponds to a value of Di which is a signed digit given as:
                                          D            i                          m              1                                =                                    y                              L                i                                      +                                          ∑                                  j                  =                  0                                                                      m                    i                                    -                  3                                            ⁢                                                y                                      j                    +                                          (                                                                        L                          i                                                +                        1                                            )                                                                      ·                                  2                  j                                                      -                                          y                                  L                                      (                                          i                      +                      1                                        )                                                              ·                              2                                                      m                    i                                    -                  2                                                                    ⁢                                  ⁢                  (                      where            ,                                          m                i                            ≥              3                                )                ⁢                                  ⁢                              L            i                    =                                                    ∑                                  j                  =                  1                                                  i                  -                  1                                            ⁢                              m                j                                      -                          i              ⁢                                                          (                              where                ,                                                      if                    ⁢                                                                                  ⁢                    i                                    =                  1                                ,                                                      then                    ⁢                                                                                  ⁢                                                                  ∑                                                  j                          =                          1                                                                          i                          -                          1                                                                    ⁢                                              m                        j                                                                              =                  0                                            )                                                          Eq        .                                  ⁢        1            
The conventional method which finds a minimal signed digit with variable multi-bit based on Booth's algorithm as above requires an additional addition operation for computing a value of signed digit SD generated as the number of bits increases.
FIGS. 2A and 2B are views illustrating one example of a conventional method for finding a minimal signed digit using variable multi-bit coding.
Referring to FIGS. 2A and 2B, the conventional method which finds a minimal signed digit with the variable multi-bit coding employs Eq. 1 set forth above. That is, Di which is a signed digit SD is obtained by calculating Li by Eq. 1 above. At this time, it is possible to confirm whether a multiplicand Y of multiplication operation is identical to the original value thereof, as in FIGS. 2A and 2B. The multiplicand Y is calculated as follows:
                    Y        =                              ∑                          i              =              1                        l                    ⁢                                    D              i              mi                        ·                          2                              Li                +                1                                                                        Eq        .                                  ⁢        2            
FIG. 2A describes a 2's complement representation of fixed coefficient “−2098”.
Here, if the number of signed digits SD, i.e., l=4, and m1=5, m2=3, m3=6 and m4=6, Li can be obtained by using Eq. 1 as:L1=−1L2=m1−2=3L3=m1+m2−3=5L4=m1+m2+m3−4=10L5=m1+m2+m3+m4−5=12(Not used)  Eq. 3
Next, Di can be found from Li obtained from Eq. 3 above, the result of which is “Y=−2098”, as follows:D15=0+0·20+1·21+1·22−1·23=−2D23=1+0·20−0·21=1D36=0+1·20+1·21+1·22+1·23−1·24=−1D46=1+0·20+1·21+1·22+1·23−1·24=−1Y=−2·20+1·24−1·26−1·211=−2098  Eq. 4
As another example, FIG. 2B shows a 2's complement representation of fixed coefficient “3784”.
Here, if the number of signed digits SD, i.e., l=4, and m1=7, m2=3, m3=5 and m4=3, Li can be obtained by using Eq. 1, as follows:L1=−1L2=m1−2=5L3=m1+m2−3=7L4=m1+m2+m3−4=11L5=m1+m2+m3+m4−5=13(Not used)  Eq. 5
Next, Di can be found from Li obtained from Eq. 5 above, the result of which is “Y=3784”, as follows:D17=0+0·20+0·21+0·22+1·23+0·24−0·25=8D23=0+1·20−1·21=−1D35=1+0·20+1·21+1·22−1·23=−1D43=1+0·20−0·21=1Y=8·20−1·26−1·28+1·212=3784  Eq. 6
As described above, the conventional method requires an additional addition operation for computing a signed digit SD, i.e., Li, as given in FIGS. 2A and 2B, generated as the number of bits increases.
Consequently, there is a need for a method which finds a minimal signed digit with variable multi-bit coding based on Booth's algorithm while solving the above problems.